/*
 * 基数排序
 * @Author: yuzezhong 
 * @Date: 2019-06-09 10:21:19 
 * @Last Modified by: yuzezhong
 * @Last Modified time: 2019-06-09 14:25:19
 */
#include <iostream>
#include <vector>
#include <memory.h>

using namespace std;

int max_digit(vector<int> vec)
{
    int base = 10;
    int digit = 1;
    for (int i = 0; i < vec.size(); i++)
    {
        if (vec.at(i) > base)
        {
            digit++;
            base *= 10;
        }
    }
    return digit;
}

void radix_sort(vector<int> &vec)
{
    int digit = max_digit(vec);
    int base = 1;
    int vec_size = vec.size();
    vector<int> tmp(vec_size); //存放中间结果的临时数组
    vector<int> count(10); //存放某一位相同数字个数
    while (digit--)                       //做digit次的计数排序
    {
        //统计某一位相同数字个数
        count.clear();
        count.resize(10);
        // cout << (*count).size() << endl;
        for (size_t i = 0; i < vec_size; i++)
        {
            int index = vec.at(i) / base % 10;
            count.at(index) += 1;
        }

        for (int j = 1; j < 10; j++)
            count[j] += count[j - 1]; //将tmp中的位置依次分配给每个桶

        for (int j = vec_size - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
        {
            int k = (vec.at(j) / base) % 10;
            tmp[--count.at(k)] = vec.at(j);
        }

        //将tmp数组中的元素拷回原数组
        vec.swap(tmp);
        base *= 10;
    }
}

int main()
{
    vector<int> vec(10);
    for (auto &&i : vec)
    {
        i = rand() % 100 + 1;
    }

    radix_sort(vec);

    for (auto &&i : vec)
    {
        cout << i << ",";
    }

    cout << endl;
    return 0;
}
